package main

import (
	"fmt"
	"sync"
)

// LinkStack 链表栈实现， 后进先出
type LinkStack struct {
	root *LinkNode 		// 链表头节点
	size int				// 栈的元素数量
	lock sync.Mutex			// 为了并发安全使用的锁
}

// LinkNode 链表节点
type LinkNode struct {
	Next *LinkNode
	Value string
}

// Push 入栈操作(头插法)
func (stack *LinkStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	// 如果栈顶为空，那么增加节点
	if stack.root == nil {
		stack.root = new(LinkNode)
		stack.root.Value = v
	} else {
		// 否则新元素插入链表的头部
		preNode := stack.root

		// 新节点
		newNode := new(LinkNode)
		newNode.Value = v

		newNode.Next = preNode
		stack.root = newNode
	}
	stack.size = stack.size + 1
}

// Pop 出栈操作（头删法）
func (stack *LinkStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	// 如果链栈为空
	if (stack.size == 0) {
		panic("empty")
	}
	// 获取头部元素的值
	topNode := stack.root
	v := topNode.Value

	// 删除头部节点
	stack.root = topNode.Next

	// 栈中元素数量 - 1
	stack.size = stack.size - 1

	return v
}


// Peek 获取栈顶元素
func (stack *LinkStack) Peek() string {
	// 栈中元素为空
	if stack.size == 0 {
		panic("empty")
	}

	// 顶部元素值
	v := stack.root.Value
	return v
}

// Size 获取栈的大小
func (stack *LinkStack) Size() int {
	return stack.size
}

// IsEmpty 判断栈是否为空
func (stack *LinkStack) IsEmpty() bool {
	return stack.size == 0
}

func main() {

	linkStack := new(LinkStack)
	linkStack.Push("cat")
	linkStack.Push("dog")
	linkStack.Push("hen")
	fmt.Println("size:", linkStack.Size())
	fmt.Println("pop:", linkStack.Pop())
	fmt.Println("pop:", linkStack.Pop())
	fmt.Println("size:", linkStack.Size())
	linkStack.Push("drag")
	fmt.Println("pop:", linkStack.Pop())

}































